<!DOCTYPE html>



  


<html class="theme-next gemini use-motion" lang="zh-Hans">
<head>
  <meta charset="UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"/>
<meta name="theme-color" content="#222">









<meta http-equiv="Cache-Control" content="no-transform" />
<meta http-equiv="Cache-Control" content="no-siteapp" />
















  
  
  <link href="/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css" />







<link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css" />

<link href="/css/main.css?v=5.1.4" rel="stylesheet" type="text/css" />


  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png?v=5.1.4">


  <link rel="mask-icon" href="/images/logo.svg?v=5.1.4" color="#222">





  <meta name="keywords" content="Dynamic Programming,动态规划," />





  <link rel="alternate" href="/atom.xml" title="Victor Su's Blog" type="application/atom+xml" />






<meta name="description" content="最近刚开始入坑LeetCode，遇到了动态规划的题目。以前只是知道动态规划，用得很少，基本是局限在用空间换时间等“Memoization”之类的技巧，最近才找了一些资料，对动态规划有了真正的了解。但因为做的题目太少，有一些地方还不太明白，先记录下来，以后慢慢加深理解。">
<meta name="keywords" content="Dynamic Programming,动态规划">
<meta property="og:type" content="article">
<meta property="og:title" content="初识动态规划的一点理解">
<meta property="og:url" content="https://swz.software/2018/01/28/first-understanding-of-dynamic-programming/index.html">
<meta property="og:site_name" content="Victor Su&#39;s Blog">
<meta property="og:description" content="最近刚开始入坑LeetCode，遇到了动态规划的题目。以前只是知道动态规划，用得很少，基本是局限在用空间换时间等“Memoization”之类的技巧，最近才找了一些资料，对动态规划有了真正的了解。但因为做的题目太少，有一些地方还不太明白，先记录下来，以后慢慢加深理解。">
<meta property="og:locale" content="zh-Hans">
<meta property="og:updated_time" content="2020-07-28T09:03:16.507Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="初识动态规划的一点理解">
<meta name="twitter:description" content="最近刚开始入坑LeetCode，遇到了动态规划的题目。以前只是知道动态规划，用得很少，基本是局限在用空间换时间等“Memoization”之类的技巧，最近才找了一些资料，对动态规划有了真正的了解。但因为做的题目太少，有一些地方还不太明白，先记录下来，以后慢慢加深理解。">



<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/',
    scheme: 'Gemini',
    version: '5.1.4',
    sidebar: {"position":"left","display":"post","offset":12,"b2t":false,"scrollpercent":false,"onmobile":false},
    fancybox: true,
    tabs: true,
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    duoshuo: {
      userId: '0',
      author: '博主'
    },
    algolia: {
      applicationID: '5NDKO7FZQ8',
      apiKey: '82a8ad411137d103431806a0c32bf181',
      indexName: 'blog',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"没有找到任何结果：${query}","hits_stats":"找到 ${hits} 条结果（用时 ${time} ms）"}
    }
  };
</script>



  <link rel="canonical" href="https://swz.software/2018/01/28/first-understanding-of-dynamic-programming/"/>





  <title>初识动态规划的一点理解 | Victor Su's Blog</title>
  








</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-Hans">

  
  
    
  

  <div class="container sidebar-position-left page-post-detail">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/"  class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">Victor Su's Blog</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
      
        <p class="site-subtitle">随便记点什么吧</p>
      
  </div>

  <div class="site-nav-toggle">
    <button>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-home"></i> <br />
            
            首页
          </a>
        </li>
      
        
        <li class="menu-item menu-item-tags">
          <a href="/tags/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-tags"></i> <br />
            
            标签
          </a>
        </li>
      
        
        <li class="menu-item menu-item-categories">
          <a href="/categories/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-th"></i> <br />
            
            分类
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/archives/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-archive"></i> <br />
            
            归档
          </a>
        </li>
      

      
        <li class="menu-item menu-item-search">
          
            <a href="javascript:;" class="popup-trigger">
          
            
              <i class="menu-item-icon fa fa-search fa-fw"></i> <br />
            
            搜索
          </a>
        </li>
      
    </ul>
  

  
    <div class="site-search">
      
  
  <div class="algolia-popup popup search-popup">
    <div class="algolia-search">
      <div class="algolia-search-input-icon">
        <i class="fa fa-search"></i>
      </div>
      <div class="algolia-search-input" id="algolia-search-input"></div>
    </div>

    <div class="algolia-results">
      <div id="algolia-stats"></div>
      <div id="algolia-hits"></div>
      <div id="algolia-pagination" class="algolia-pagination"></div>
    </div>

    <span class="popup-btn-close">
      <i class="fa fa-times-circle"></i>
    </span>
  </div>




    </div>
  
</nav>



 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            

  <div id="posts" class="posts-expand">
    

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="https://swz.software/2018/01/28/first-understanding-of-dynamic-programming/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="Victor Su">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Victor Su's Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">初识动态规划的一点理解</h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2018-01-28T16:58:31+08:00">
                2018-01-28
              </time>
            

            

            
          </span>

          
            <span class="post-category" >
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/LeetCode/" itemprop="url" rel="index">
                    <span itemprop="name">LeetCode</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        <p>最近刚开始入坑LeetCode，遇到了动态规划的题目。以前只是知道动态规划，用得很少，基本是局限在用空间换时间等“Memoization”之类的技巧，最近才找了一些资料，对动态规划有了真正的了解。但因为做的题目太少，有一些地方还不太明白，先记录下来，以后慢慢加深理解。</p>
<a id="more"></a>
<h2 id="什么是动态规划"><a href="#什么是动态规划" class="headerlink" title="什么是动态规划"></a>什么是动态规划</h2><h3 id="定义："><a href="#定义：" class="headerlink" title="定义："></a>定义：</h3><p><a href="https://en.wikipedia.org/wiki/Dynamic_programming" target="_blank" rel="noopener">Wikipedia</a>:</p>
<blockquote>
<p>Dynamic programming (also known as dynamic optimization) is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions.</p>
</blockquote>
<p>动态规划的核心在于将一个不好解决的问题拆分为子问题，递归地拆分下去之后，规模很小（如N=1）时候的子问题很容易解决，结合拆分过程中得到的状态转移方程（解决了N&lt;=k -&gt; N=k+1怎么变）即可解决原问题。动态规划如果找到了状态转移方程就很好解决，而记忆化、递归、递推等等都只是一些技巧，并不是动态规划的核心。</p>
<h3 id="状态与状态转移方程："><a href="#状态与状态转移方程：" class="headerlink" title="状态与状态转移方程："></a>状态与状态转移方程：</h3><p>个人非官方理解：一个规模为N=k的问题可以理解为第k个状态，记N=k时待求的量为F<sub>k</sub>，那么怎么由N&lt;=k得到N=k+1，即F<sub>k+1</sub>=f(F<sub>&lt;=k</sub>)就是状态转移方程。<strong>动态规划最难的地方便在于怎么合适地定义状态，使得能够找到状态转移方程，找到方程了就相当于找到了怎么将原问题拆分成子问题减小规模。</strong></p>
<h2 id="一些例子："><a href="#一些例子：" class="headerlink" title="一些例子："></a>一些例子：</h2><h3 id="Fibonacci序列"><a href="#Fibonacci序列" class="headerlink" title="Fibonacci序列"></a>Fibonacci序列</h3><p>Fibonacci序列：1，1，2，3，5，8，13 ……</p>
<p>问题：求Fibonacci序列中第n个元素</p>
<p>比较明显，记待求的量（Fibonacci序列中第n个元素）为F<sub>n</sub>，由递推公式即可以获得状态转移方程F<sub>n</sub> = F<sub>n-1</sub> + F<sub>n-2</sub></p>
<h3 id="最长上升子序列"><a href="#最长上升子序列" class="headerlink" title="最长上升子序列"></a>最长上升子序列</h3><p>问题：给定一个长度为n数列，求其最长上升子数列的长度。<br>以1 7 2 8 3 4为例。这个数列的最长上升子数列是 1 2 3 4，长度为4；次长的长度为3， 包括 1 7 8; 1 2 3 等。</p>
<p>如果仍像Fibonacci序列那样采取最直观的方式定义状态，记该数列（长度为n）的最长上升子数列的长度为F<sub>n</sub>，求状态转移方程时将用到F<sub>k</sub> ( k &lt; n ) ，而F<sub>k</sub> ( k &lt; n ) 不是确定的（只知道长度是k），没有意义。我们需要一个确定的规模缩小的状态，所以需要在原数列中特定位置截取长为k的子数列。一种取法是，原数列L，取L[1-&gt;k][注1]作为规模缩小后的状态，这样子保证了，最初的状态是L[1-&gt;n]没有变，而随着规模缩小，每次得到的数列依然是确定的。</p>
<p>因此，我们将问题表述调整为：给定一个长度为n数列，求其子数列L[1-&gt;n]的最长上升子数列长度。记其子数列L[1-&gt;n]的最长上升子数列长度为F<sub>n</sub>。尝试得到状态转移方程，思路过程如下：</p>
<p>已知序列a b c d e f g h的最长上升子序列是a b d f，找a b c d e f g h i最长上升子序列，若i = f，则必定是a b d f i（长度为4 + 1 = 5），若i &lt;= f，则需要得到原先的序列第二长的上升子序列（如a c g），如果i &gt; g，则最长子序列可以是a c g i或者a b d f。（虽然此时长度都是4，但是不单需要知道长度，还得记录子序列的最后一个元素，因为判断i与f关系的时候用到了。因此这里需要知道第二长的序列，并求出最长的序列。）而原先的序列的第二长的子序列不好算，若尝试算如下：</p>
<p>设F<sub>n</sub> = ( l<sub>Bn</sub>, B<sub>n</sub>, l<sub>Cn</sub>, C<sub>n</sub> ) 。B<sub>n</sub>是L[1-&gt;n]的最长上升子序列的最后一个元素构成的列表（最长上升子序列可能不止一个），l<sub>Bn</sub>是L[1-&gt;n]的最长上升子序列的长度，C<sub>n</sub>是L[1-&gt;n]的第二长上升子序列的最后一个元素构成的列表，l<sub>Bn</sub> 是L[1-&gt;n]的第二长上升子序列的长度。（例如上述序列a -&gt; h即为：(4, [f], 3, [g])。）设了4个量，因为由上面分析过程看出，从n-1状态得到n状态的最长上升子序列长度，最少都需要这四个量。接着推导状态转移方程就会发现，由F<sub>n-1</sub>计算C<sub>n</sub>的时候，是需要知道n-1状态下的第三长的上升子序列的，而目前设的4个量中并没有……也就是还得引入D<sub>n</sub>，l<sub>Dn</sub>……这样子就导致需要引入F<sub>n</sub>等等，没办法计算。<em>（如果不需要引入新的量的话，理论上是可以这么计算的。）</em></p>
<p>以上是经过查找了不少资料，又过了几天之后自己尝试推导的结果。所以说寻找合适的状态定义还是蛮困难的Orz。</p>
<p>怎么做？<strong>并不需要直接得到结果（最长上升子序列长度），可以得到一系列相关结果后从中选择合适的。把问题改为求一些相关结果，此时可以加一些限制，使得问题容易解决。</strong> 而这里可以限制以第几个元素开头或者结尾。</p>
<p>问题改成：在长为n的这个序列中，求以第k个元素结尾的最长上升子序列的长度。该序列的最长上升子序列的长度（原问题），是这个问题所有结果的最大值。故令F<sub>k</sub> 为第k个元素结尾的最长上升子序列的长度，则有状态方程：</p>
<p>F<sub>k</sub> = max{ F<sub>i</sub> + 1 | L[i] &lt; L[k], i = from 1 to (k - 1) }，即对i从1到k-1（所有比k小的状态），若L[i] &lt; L[k]，则把这个值 +1 之后取出来，所有取出来的值取最大即得到F<sub>k</sub>。（需要L[i] &lt; L[k]是因为待求的是以第k个元素结尾的。）</p>
<p><em><u>Notes:</u></em></p>
<ol>
<li><p>与上一个想法不一样的在于，缩小规模不是靠考虑小一点的子串L[1-&gt;k]，而是规定了子序列结尾字符的位置。从而避免了在上一个想法中，确定子序列长度的时候需要用上子序列最后一个字符，导致需要多设一个量记录子序列是什么的困境。</p>
</li>
<li><p><strong>状态转移方程中由F<sub>k-1</sub>求F<sub>k</sub>不好求，这里不管k-1状态是什么样， 直接由小于k的所有合适状态中取最大值。</strong></p>
</li>
</ol>
<h3 id="最长回文子序列"><a href="#最长回文子序列" class="headerlink" title="最长回文子序列"></a>最长回文子序列</h3><p>问题：给定一个字符串序列，找出最长的回文子序列长度。<br>例如absdbhjah，回文子序列有abdba，hjh等，最长回文子序列长度是5。</p>
<p>如果令F<sub>k</sub>=L[1-&gt;k]的最长回文子序列长度，由F<sub>k-1</sub>求F<sub>k</sub>时，末尾多了一个元素，要知道F<sub>k</sub>有没有比F<sub>k-1</sub>大，需要知道F<sub>k-1</sub>的时候的回文子序列第一个元素是不是L[1]，这个可以通过引入多一个量或者修改问题描述增加开始位置限制等来解决。但是这些方法对于第一个元素不是L[1]的情况依然不好求F<sub>k</sub>。这里可以令F<sub>m,n</sub>=L[m-&gt;n]的最长回文子序列。原问题则是求F<sub>1,N</sub>。则状态转移方程如下：</p>
<p>F<sub>m,n</sub> = F<sub>m+1,n-1</sub> + 2,  L[m] == L[n]<br>F<sub>m,n</sub> = max{ F<sub>m,n-1</sub> , F<sub>m+1,n</sub> },  L[m] != L[n]</p>
<p><u><em>Notes:</em></u></p>
<ol>
<li><p>同样的，在L[m] != L[n]的情况，反正回文子序列不会同时包含L[m]与L[n]，那么最长回文子序列要么包含L[m]不包含L[n]（F<sub>m,n-1</sub>），要么那么最长回文子序列要么包含L[n]不包含L[m]（F<sub>m+1,n</sub>），要么都不包含（F<sub>m,n-1</sub>或者F<sub>m+1,n</sub>，两者相等），直接取最大值即可，不用去判断</p>
</li>
<li><p>当自变量有两个及以上（m, n两个）时，<strong>由F<sub>m,n</sub>入手思考，怎么才能得到F<sub>m,n</sub>（可以用上F<sub>i,j</sub>（i &lt; m, j &lt; n））</strong>；而不要倒过来想F<sub>m,n</sub>怎么得到F<sub>m+1,n+1</sub>。</p>
</li>
</ol>
<p>另外一种考虑：</p>
<p>令F<sub>m,n</sub> = L中以L[m]开头，L[n]结尾的最长回文子序列，则记原问题为P<sub>N</sub>，P<sub>N</sub> = T<sub>1,N</sub> = max{ F<sub>i,j</sub> i from 1 to N, j from 1 to N, i &lt; j }，则得到状态转移方程：</p>
<p>F<sub>m,n</sub> = 0,  L[m] != L[n]<br>F<sub>m,n</sub> = T<sub>m+1,n-1</sub> + 2,  L[m] == L[n]</p>
<p>但是耗时明显要比上一个方法大，每一个T的计算都要比较n<sup>2</sup>个数据。（如果优化，对反复用到的数据（是F不是T，T只是max的记号而已，将max{}代入T来理解，T<sub>i,j</sub>与T<sub>i-1,j-1</sub>没有关系）做缓存，依然无法避免反复比较的问题。）</p>
<h3 id="01背包问题"><a href="#01背包问题" class="headerlink" title="01背包问题"></a>01背包问题</h3><p>问题：有N件物品和一个容量为V的背包。第i件物品的占用空间是cost[i]，价值是value[i]。求解将哪些物品装入背包可使价值总和最大。</p>
<p>如果令F<sub>v</sub>=将这些物品（N个）放入容量为V的背包中的最大价值，则状态转移方程不好求，因为背包容量增大的时候，可以取出一些物品再放入一些，可能能产生更大价值。所以这里如同上一个例子（回文序列），将另一个影响量物品数也作为<em>自变量</em>。如下：</p>
<p>令F<sub>n,v</sub>=将前n件物品放入容量为v的背包中所能获得的最大价值。则可得到状态转移方程：</p>
<p>F<sub>n,v</sub> = max{ F<sub>n-1,v</sub>, F<sub>n-1,v-cost[n]</sub> + value[n] }<br><strong>即分成两种情况，最后一个物品放与不放。</strong> 如果不放，等同于前n-1件物品放入容量为v的背包中获得的最大价值F<sub>n-1,v</sub>。如果放，需要先将背包腾出足够空间，剩下空间放前n-1个物品，所以是F<sub>n-1,v-cost[n]</sub> + value[n]，两者直接比较取最大值。</p>
<h3 id="其他例子"><a href="#其他例子" class="headerlink" title="其他例子"></a>其他例子</h3><p>知乎答主<a href="https://www.zhihu.com/people/crackinterview/activities" target="_blank" rel="noopener">ninechapter</a>在<a href="https://www.zhihu.com/question/23995189/answer/151764127" target="_blank" rel="noopener">什么是动态规划？动态规划的意义是什么？ - ninechapter的回答 - 知乎</a>提到：</p>
<blockquote>
<p>动态规划的常见类型分为：</p>
<ul>
<li>矩阵型</li>
<li>序列型</li>
<li>双序列型</li>
<li>划分型</li>
<li>区间型</li>
<li>背包型</li>
<li>状态压缩型</li>
<li>树型</li>
</ul>
</blockquote>
<p>而因为目前遇到的题目不多，先记下来，以后遇到再留意。</p>
<h2 id="动态规划实现的优化"><a href="#动态规划实现的优化" class="headerlink" title="动态规划实现的优化"></a>动态规划实现的优化</h2><h3 id="自顶向下"><a href="#自顶向下" class="headerlink" title="自顶向下"></a>自顶向下</h3><p>通常使用递归，求f(k)需要先求f(k-1)-&gt;f(k-2)…可以将存在重复计算的部分在表中记录下来，之后遇到不需要计算而是改为查表。如Fibonacci序列，F(5)-&gt;需要F(4)+F(3)，而在计算F(4)的时候又要计算F(3)+F(2)，重复计算。所以可以用表记录F(x)，当F(x)已存在的时候直接查表。</p>
<h3 id="自下向顶"><a href="#自下向顶" class="headerlink" title="自下向顶"></a>自下向顶</h3><p>通常使用递推，f(n)状态转移方程已知，先求f(1)-&gt;f(2)-&gt;…-&gt;f(n)。同样可以考虑记录重复计算部分，并且自下向顶更容易优化占用的空间。如Fibonacci序列，自顶向下空间复杂度是O(n)，而如果从状态转移方程入手自下向顶，F<sub>n</sub> = F<sub>n-1</sub> + F<sub>n-2</sub> ，可以看到每求下一个数只用到前两个数，其他的数算出来之后不用保存。空间复杂度优化至O(1)。</p>
<p>01背包问题的空间复杂度优化：</p>
<p>如果记录中间结果避免重复计算，有两个自变量n，v，不做优化空间复杂度为O(N*V)，但考虑状态转移方程：F<sub>n,v</sub> = max{ F<sub>n-1,v</sub>, F<sub>n-1,v-cost[n]</sub> + value[n] }，发现计算F<sub>n,v</sub>只需要用到F<sub>n-1,x</sub> ( x &lt;= v) 的数据，即没必要保存整个N*V矩阵，只需要保存当中的两行（第n行与第n-1行）就行了。空间复杂度优化至O(2V)。实现：只用2*V矩阵，当计算第n行时，可以将数据保存在矩阵中的第n % 2行。</p>
<p>进一步优化：上述是记录第n行与第n-1行，能否只记录一行？当计算第n行时，记录的是第n-1行，如果每计算第n行的一个即覆盖第n-1行的一个记录，并保证这个记录之后不会用到即可优化，因此关键在于第n行的元素的计算顺序。状态转移方程可以看出，计算F<sub>n,v</sub>用到的元素是F<sub>n-1,x</sub> ( x &lt;= v) ，所以计算第n行时若是从(n, max)计算到(n, 1)，便能保证没有需要用到的元素(n, x)都没有被覆盖。空间复杂度优化至O(V)。</p>
<h2 id="其他资料"><a href="#其他资料" class="headerlink" title="其他资料"></a>其他资料</h2><p>学习的过程中参考了不少资料，以下是遇到的一些比较有用的。</p>
<ul>
<li><a href="https://www.zhihu.com/question/23995189" target="_blank" rel="noopener">什么是动态规划？动态规划的意义是什么？</a></li>
<li><a href="https://www.zhihu.com/question/39948290" target="_blank" rel="noopener">如何理解动态规划？</a></li>
<li><a href="https://www.cnblogs.com/William-xh/p/7305877.html" target="_blank" rel="noopener">01背包问题的详细概述</a></li>
<li><a href="https://github.com/tianyicui/pack" target="_blank" rel="noopener">背包九讲</a></li>
</ul>
<h2 id="待解决的问题"><a href="#待解决的问题" class="headerlink" title="待解决的问题"></a>待解决的问题</h2><ul>
<li><p>动态规划问题中，从数学的角度时间复杂度应该如何求解？尤其是当使用了递归和记忆化的时候？</p>
</li>
<li><p>看到一些描述说到动态规划与图论的关系，但是不太明白是怎么理解：</p>
<blockquote>
<p>所有的动态规划问题都可以转变为状态空间内大量可行状态点和有效转移构成的图的从初始状态到最终状态的最短路问题。</p>
<p>动态规划其实是一个广义有向无环图上的最短路问题。这个图怎么建立？将所有的状态都抽象为节点。从节点i到节点j的边权看做是从状态i到状态j所作出决策后的payoff。那么，我们的目标状态就是求解，从一个初始状态到最终状态的最短路问题。</p>
<p>只要图建出来了，用拓扑排序，dfs，bfs甚至最短路算法都能解。</p>
</blockquote>
</li>
<li><p>另外有知乎答主从图的角度理解动态规划并给出了一个据说更容易操作的方法，但是不太理解。<a href="https://www.zhihu.com/question/39948290/answer/83942329" target="_blank" rel="noopener">如何理解动态规划？ - 冒泡的回答 - 知乎</a></p>
</li>
</ul>
<p>[注1]: L[1-&gt;k]：个人临时用的一个写法，代表列表L中，从第1个元素开始，到第k个元素截止（包含第1个和第k个）得到的子列表。</p>

      
    </div>
    
    
    

    

    

    
      <div>
        <ul class="post-copyright">
  <li class="post-copyright-author">
    <strong>本文作者：</strong>
    Victor Su
  </li>
  <li class="post-copyright-link">
    <strong>本文链接：</strong>
    <a href="https://swz.software/2018/01/28/first-understanding-of-dynamic-programming/" title="初识动态规划的一点理解">https://swz.software/2018/01/28/first-understanding-of-dynamic-programming/</a>
  </li>
  <li class="post-copyright-license">
    <strong>版权声明： </strong>
    本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/3.0/" rel="external nofollow" target="_blank">CC BY-NC-SA 3.0</a> 许可协议。转载请注明出处！
  </li>
</ul>

      </div>
    

    <footer class="post-footer">
      
        <div class="post-tags">
          
            <a href="/tags/Dynamic-Programming/" rel="tag"># Dynamic Programming</a>
          
            <a href="/tags/动态规划/" rel="tag"># 动态规划</a>
          
        </div>
      

      
      
        <div class="post-widgets">
        

        

        
          
          <div id="needsharebutton-postbottom">
            <span class="btn">
              <i class="fa fa-share-alt" aria-hidden="true"></i>
            </span>
          </div>
        
        </div>
      
      

      

      
      
    </footer>
  </div>
  
  
  
  </article>



    <div class="post-spread">
      
    </div>
  </div>


          </div>
          


          

  
    <div class="comments" id="comments">
      <div id="lv-container" data-id="city" data-uid="MTAyMC8zMzY4NC8xMDIzOQ=="></div>
    </div>

  



        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    
    <div class="sidebar-inner">

      

      
        <ul class="sidebar-nav motion-element">
          <li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap">
            文章目录
          </li>
          <li class="sidebar-nav-overview" data-target="site-overview-wrap">
            站点概览
          </li>
        </ul>
      

      <section class="site-overview-wrap sidebar-panel">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
            
              <p class="site-author-name" itemprop="name">Victor Su</p>
              <p class="site-description motion-element" itemprop="description">Where there's a will, there's a way.</p>
          </div>

          <nav class="site-state motion-element">

            
              <div class="site-state-item site-state-posts">
              
                <a href="/archives/">
              
                  <span class="site-state-item-count">1</span>
                  <span class="site-state-item-name">日志</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-categories">
                <a href="/categories/index.html">
                  <span class="site-state-item-count">1</span>
                  <span class="site-state-item-name">分类</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-tags">
                <a href="/tags/index.html">
                  <span class="site-state-item-count">2</span>
                  <span class="site-state-item-name">标签</span>
                </a>
              </div>
            

          </nav>

          
            <div class="feed-link motion-element">
              <a href="/atom.xml" rel="alternate">
                <i class="fa fa-rss"></i>
                RSS
              </a>
            </div>
          

          
            <div class="links-of-author motion-element">
                
                  <span class="links-of-author-item">
                    <a href="https://github.com/VictorSu000" target="_blank" title="GitHub">
                      
                        <i class="fa fa-fw fa-github"></i>GitHub</a>
                  </span>
                
                  <span class="links-of-author-item">
                    <a href="mailto:victorsuwww@foxmail.com" target="_blank" title="E-Mail">
                      
                        <i class="fa fa-fw fa-envelope"></i>E-Mail</a>
                  </span>
                
                  <span class="links-of-author-item">
                    <a href="https://t.me/VictorSu000" target="_blank" title="Telegram">
                      
                        <i class="fa fa-fw fa-telegram"></i>Telegram</a>
                  </span>
                
            </div>
          

          
          

          
          

          

        </div>
      </section>

      
      <!--noindex-->
        <section class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active">
          <div class="post-toc">

            
              
            

            
              <div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#什么是动态规划"><span class="nav-number">1.</span> <span class="nav-text">什么是动态规划</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#定义："><span class="nav-number">1.1.</span> <span class="nav-text">定义：</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#状态与状态转移方程："><span class="nav-number">1.2.</span> <span class="nav-text">状态与状态转移方程：</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#一些例子："><span class="nav-number">2.</span> <span class="nav-text">一些例子：</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#Fibonacci序列"><span class="nav-number">2.1.</span> <span class="nav-text">Fibonacci序列</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#最长上升子序列"><span class="nav-number">2.2.</span> <span class="nav-text">最长上升子序列</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#最长回文子序列"><span class="nav-number">2.3.</span> <span class="nav-text">最长回文子序列</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#01背包问题"><span class="nav-number">2.4.</span> <span class="nav-text">01背包问题</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#其他例子"><span class="nav-number">2.5.</span> <span class="nav-text">其他例子</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#动态规划实现的优化"><span class="nav-number">3.</span> <span class="nav-text">动态规划实现的优化</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#自顶向下"><span class="nav-number">3.1.</span> <span class="nav-text">自顶向下</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#自下向顶"><span class="nav-number">3.2.</span> <span class="nav-text">自下向顶</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#其他资料"><span class="nav-number">4.</span> <span class="nav-text">其他资料</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#待解决的问题"><span class="nav-number">5.</span> <span class="nav-text">待解决的问题</span></a></li></ol></div>
            

          </div>
        </section>
      <!--/noindex-->
      

      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright">&copy; 2018 &mdash; <span itemprop="copyrightYear">2020</span>
  <span class="with-love">
    <i class="fa fa-user"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">Victor Su</span>

  
</div>


  <div class="powered-by">由 <a class="theme-link" target="_blank" href="https://hexo.io">Hexo</a> 强力驱动</div>



  <span class="post-meta-divider">|</span>



  <div class="theme-info">主题 &mdash; <a class="theme-link" target="_blank" href="https://github.com/iissnan/hexo-theme-next">NexT.Gemini</a> v5.1.4</div>




        







        
      </div>
    </footer>

    
      <div class="back-to-top">
        <i class="fa fa-arrow-up"></i>
        
      </div>
    

    

  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  












  
  
    <script type="text/javascript" src="/lib/jquery/index.js?v=2.1.3"></script>
  

  
  
    <script type="text/javascript" src="/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script>
  

  
  
    <script type="text/javascript" src="/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>
  


  


  <script type="text/javascript" src="/js/src/utils.js?v=5.1.4"></script>

  <script type="text/javascript" src="/js/src/motion.js?v=5.1.4"></script>



  
  


  <script type="text/javascript" src="/js/src/affix.js?v=5.1.4"></script>

  <script type="text/javascript" src="/js/src/schemes/pisces.js?v=5.1.4"></script>



  
  <script type="text/javascript" src="/js/src/scrollspy.js?v=5.1.4"></script>
<script type="text/javascript" src="/js/src/post-details.js?v=5.1.4"></script>



  


  <script type="text/javascript" src="/js/src/bootstrap.js?v=5.1.4"></script>



  


  




	





  





  
    <script type="text/javascript">
      (function(d, s) {
        var j, e = d.getElementsByTagName(s)[0];
        if (typeof LivereTower === 'function') { return; }
        j = d.createElement(s);
        j.src = 'https://cdn-city.livere.com/js/embed.dist.js';
        j.async = true;
        e.parentNode.insertBefore(j, e);
      })(document, 'script');
    </script>
  












  




  
  
  
  <link rel="stylesheet" href="/lib/algolia-instant-search/instantsearch.min.css">

  
  
  <script src="/lib/algolia-instant-search/instantsearch.min.js"></script>
  

  <script src="/js/src/algolia-search.js?v=5.1.4"></script>



  

  

  
<script>
(function(){
    var bp = document.createElement('script');
    var curProtocol = window.location.protocol.split(':')[0];
    if (curProtocol === 'https') {
        bp.src = 'https://zz.bdstatic.com/linksubmit/push.js';        
    }
    else {
        bp.src = 'http://push.zhanzhang.baidu.com/push.js';
    }
    var s = document.getElementsByTagName("script")[0];
    s.parentNode.insertBefore(bp, s);
})();
</script>


  
  
  
  <link rel="stylesheet" href="/lib/needsharebutton/needsharebutton.css">

  
  
  <script src="/lib/needsharebutton/needsharebutton.js"></script>

  <script>
    
      pbOptions = {};
      
          pbOptions.iconStyle = "box";
      
          pbOptions.boxForm = "horizontal";
      
          pbOptions.position = "bottomCenter";
      
          pbOptions.networks = "Weibo,Douban,QQZone,Twitter,Facebook,Evernote";
      
      new needShareButton('#needsharebutton-postbottom', pbOptions);
    
    
  </script>

  

  

  

  

</body>
</html>
